#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int ans = 0, mx = values[0];
        for (int j = 1; j < values.size(); ++j)
        {
            ans = max(ans, mx + values[j] - j);
            mx = max(mx, values[j] + j);
        }
        return ans;
    }

    struct ListNode {
        int val;
        ListNode* next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode* next) : val(x), next(next) {}
        
    };

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        auto left = dummy, right = dummy;
        while (n--)
            right = right->next;
        while (right->next)
        {
            left = left->next;
            right = right->next;
        }
        left->next = left->next->next;
        return dummy->next;
    }

    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        auto matrix_new = matrix;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                matrix_new[j][n - 1 - i] = matrix[i][j];
        matrix = matrix_new;
    }

    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n / 2; ++i)
            for (int j = 0; j < n; ++j)
                swap(matrix[i][j], matrix[n - 1 - i][j]);

        for (int i = 0; i < n; ++i)
            for (int j = 0; j < i; ++j)
                swap(matrix[i][j], matrix[j][i]);
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        int len = 0;
        while (head)
        {
            ++len;
            head = head->next;
        }
        ListNode* cur = dummy;
        for (int i = 0; i < len - n; ++i)
            cur = cur->next;
        cur->next = cur->next->next;
        return dummy->next;
    }

    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        dp[1][0] = 1;
        for (int i = 1; i <= m; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    int minNumberOfFrogs(string croakOfFrogs) {
        string s = "croak";
        int n = s.size();
        vector<int> hash(n);
        unordered_map<char, int> index;
        for (int i = 0; i < n; ++i)
        {
            index[s[i]] = i;
        }
        for (char& t : croakOfFrogs)
        {
            if (t == 'c')
            {
                if (hash[n - 1] != 0) --hash[n - 1];
                ++hash[0];
            }
            else
            {
                int i = index[t];
                if (hash[i - 1] == 0) return -1;
                -hash[i - 1], ++hash[i];
            }
        }
        for (int i = 0; i < n - 1; ++i)
            if (hash[i] != 0) return -1;
        return hash[n - 1];
    }
};